% Copyright 2011-2015 David Hadka.  All Rights Reserved.
%
% This file is part of the MOEA Framework User Manual.
%
% Permission is granted to copy, distribute and/or modify this document under
% the terms of the GNU Free Documentation License, Version 1.3 or any later
% version published by the Free Software Foundation; with the Invariant Section
% being the section entitled "Preface", no Front-Cover Texts, and no Back-Cover
% Texts.  A copy of the license is included in the section entitled "GNU Free
% Documentation License".

\chapter{Example: Knapsack Problem}

In this chapter, we will walk through a complete example of creating a new optimization problem and solving it using the MOEA Framework.  This example serves as a review of the topics learned thus far.  We will also introduce several new concepts such as constraint handling.

The problem we will be solving is the multiobjective version of the knapsack problem.  The knapsack problem (discussed in much detail at \webpage{http://en.wikipedia.org/wiki/Knapsack_problem}) is a famous combinatorial problem that involves choosing which items to place in a knapsack to maximize the value of the items carried without exceeding the weight capacity of the knapsack.  More formally, we are given $N$ items.  Each item has a profit, $P(i)$, and weight, $W(i)$, for $i = {1, 2, \ldots, N}$.  Let $d(i)$ represent our decision to place the $i$-th item in the knapsack, where $d(i)=1$ if the item is put into the knapsack and $d(i)=0$ otherwise.  If the knapsack has a weight capacity of $C$, then the knapsack problem is defined as:

\begin{equation*}
  \text{Maximize} \; \sum_{i=1}^{N} d(i)*P(i) \; \text{such that} \; \sum_{i=1}^{N} d(i)*W(i) \leq C
\end{equation*}

The summation on the left (which we are maximizing) calculates the total profit we gain from the items placed in the knapsack.  The summation on the right side is a constraint that ensures the items placed in the knapsack do not exceed the weight capacity of the knapsack.

The multiobjective knapsack problem that we will be solving in this section is very similar, except that we now have $2$ knapsacks to hold the items.  Additionally, the profit and weights vary depending on which knapsack is holding each item.  For example, an item will have a profit of $\$25$ and a weight of $5$ pounds in the first knapsack, but will have a profit of $\$15$ and a weight of $8$ pounds in the second knapsack.  (It may seem unusual that the weight changes, but that is how the problem is defined in the literature.)   Thus, profit is now defined by $P(i,j)$ and weight by $W(i,j)$, where the $j = {1, 2}$ term is the knapsack index.  Lastly, each knapsack defines its own capacity, $C_1$ and $C_2$.  Combining all of this, the multiobjective knapsack problem is formally defined as:

\begin{equation*}
\begin{array}{l}
  \text{Maximize} \; \sum_{i=1}^{N} d(i)*P(i,1) \; \text{such that} \; \sum_{i=1}^{N} d(i)*W(i,1) \leq C_1 \; \text{and}\\
  \text{Maximize} \; \sum_{i=1}^{N} d(i)*P(i,2) \; \text{such that} \; \sum_{i=1}^{N} d(i)*W(i,2) \leq C_2
\end{array}
\end{equation*}

Once we have a firm understanding of the optimization problem, we can now work on solving this problem.  You can find all of the code for this example in the \folder{examples/org/moeaframework/examples/ga/knapsack} folder in the source code distribution.

\section{Data Files}
We begin by developing a way to store all of the information required by the knapsack problem --- profits, weights, capacities --- in a text file.  This will let us quickly generate and run new inputs for this problem.  Fortunately, two researchers, Eckart Zitzler and Marco Laumanns, have already created a file format for multiobjective knapsack problems at \webpage{http://www.tik.ee.ethz.ch/sop/download/supplementary/testProblemSuite/}.  For example, a simple $5$ item problem instance would appear as follows.  

\begin{lstlisting}[language=plaintext]
knapsack problem specification (2 knapsacks, 5 items)
=
knapsack 1:
 capacity: +251
 item 1:
  weight: +94
  profit: +57
 item 2:
  weight: +74
  profit: +94
 item 3:
  weight: +77
  profit: +59
 item 4:
  weight: +74
  profit: +83
 item 5:
  weight: +29
  profit: +82
=
knapsack 2:
 capacity: +190
 item 1:
  weight: +55
  profit: +20
 item 2:
  weight: +10
  profit: +19
 item 3:
  weight: +97
  profit: +20
 item 4:
  weight: +73
  profit: +66
 item 5:
  weight: +69
  profit: +48
\end{lstlisting}

We will re-use this file format in this example.  One advantage is that you can download any of the example knapsack problems from \webpage{http://www.tik.ee.ethz.ch/sop/download/supplementary/testProblemSuite/} and solve them with the program we are writing.  Go ahead and save this example input file to \file{knapsack.5.2}.  We will then load and solve this data file later in this chapter.

\section{Encoding the Problem}
The next step is to decide upon the encoding for the decision variables.  Observe that we are deciding which items to place in the knapsacks.  Recalling \chptref{chpt:representations}, the bit string representation works well for situation where we are making many yes/no decisions.  For example, if $N=5$, we can represent the decision to include each item using a bit string with $5$ bits.  Each bit in the string corresponds to an item, and is set to \java{1} if the item is included and \java{0} if the item is excluded.  For instance, the bit string \java{00110} would place items 3 and 4 inside the knapsacks, excluding the rest.

\section{Implementing the Problem}
Having decided upon an encoding, we can now implement the knapsack problem as shown below.

\begin{lstlisting}[language=Java]
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.moeaframework.core.Problem;
import org.moeaframework.core.Solution;
import org.moeaframework.core.variable.BinaryVariable;
import org.moeaframework.core.variable.EncodingUtils;
import org.moeaframework.util.Vector;
import org.moeaframework.util.io.CommentedLineReader;

/**
 * Multiobjective 0/1 knapsack problem.
 */
 public class Knapsack implements Problem {

	/**
	 * The number of sacks.
	 */
	private int nsacks;

	/**
	 * The number of items.
	 */
	private int nitems;

	/**
	 * Entry {@code profit[i][j]} is the profit from including
	 * item {@code j} in sack {@code i}.
	 */
	private int[][] profit;

	/**
	 * Entry {@code weight[i][j]} is the weight incurred from
	 * including item {@code j} in sack {@code i}.
	 */
	private int[][] weight;

	/**
	 * Entry {@code capacity[i]} is the weight capacity of sack
	 * {@code i}.
	 */
	private int[] capacity;

	/**
	 * Constructs a multiobjective 0/1 knapsack problem instance
	 * loaded from the specified file.
	 * 
	 * @param file the file containing the knapsack problem
	 *        instance
	 * @throws IOException if an I/O error occurred
	 */
	public Knapsack(File file) throws IOException {
		this(new FileReader(file));
	}
	
	/**
	 * Constructs a multiobjective 0/1 knapsack problem instance
	 * loaded from the specified input stream.
	 * 
	 * @param inputStream the input stream containing the knapsack
	 *         problem instance
	 * @throws IOException if an I/O error occurred
	 */
	public Knapsack(InputStream inputStream) throws IOException {
		this(new InputStreamReader(inputStream));
	}
	
	/**
	 * Constructs a multiobjective 0/1 knapsack problem instance
	 * loaded from the specified reader.
	 * 
	 * @param reader the reader containing the knapsack problem
	 *        instance
	 * @throws IOException if an I/O error occurred
	 */
	public Knapsack(Reader reader) throws IOException {
		super();
		
		load(reader);
	}

	/**
	 * Loads the knapsack problem instance from the specified
	 * reader.
	 * 
	 * @param reader the file containing the knapsack problem
	 *        instance
	 * @throws IOException if an I/O error occurred
	 */
	private void load(Reader reader) throws IOException {
		Pattern specificationLine = Pattern.compile("knapsack problem specification \\((\\d+) knapsacks, (\\d+) items\\)");
		Pattern capacityLine = Pattern.compile(" capacity: \\+(\\d+)");
		Pattern weightLine = Pattern.compile("  weight: \\+(\\d+)");
		Pattern profitLine = Pattern.compile("  profit: \\+(\\d+)");

		CommentedLineReader lineReader = null;
		String line = null;
		Matcher matcher = null;
		
		try {
			lineReader = new CommentedLineReader(reader);
			line = lineReader.readLine(); // problem specification
			matcher = specificationLine.matcher(line);
			
			if (matcher.matches()) {
				nsacks = Integer.parseInt(matcher.group(1));
				nitems = Integer.parseInt(matcher.group(2));
			} else {
				throw new IOException("knapsack data file " +
						"not properly formatted: invalid specification " +
						"line");
			}
			
			capacity = new int[nsacks];
			profit = new int[nsacks][nitems];
			weight = new int[nsacks][nitems];
	
			for (int i = 0; i < nsacks; i++) {
				line = lineReader.readLine(); // line containing "="
				line = lineReader.readLine(); // knapsack i
				line = lineReader.readLine(); // the knapsack capacity
				matcher = capacityLine.matcher(line);
				
				if (matcher.matches()) {
					capacity[i] = Integer.parseInt(matcher.group(1));
				} else {
					throw new IOException("knapsack data file " +
							"not properly formatted: invalid capacity line");
				}
	
				for (int j = 0; j < nitems; j++) {
					line = lineReader.readLine(); // item j
					line = lineReader.readLine(); // the item weight
					matcher = weightLine.matcher(line);
					
					if (matcher.matches()) {
						weight[i][j] = Integer.parseInt(matcher.group(1));
					} else {
						throw new IOException("knapsack data file " +
								"not properly formatted: invalid weight line");
					}
	
					line = lineReader.readLine(); // the item profit
					matcher = profitLine.matcher(line);
					
					if (matcher.matches()) {
						profit[i][j] = Integer.parseInt(matcher.group(1));
					} else {
						throw new IOException("knapsack data file " +
								"not properly formatted: invalid profit line");
					}
				}
			}
		} finally {
			if (lineReader != null) {
				lineReader.close();
			}
		}
	}

	@Override
	public void evaluate(Solution solution) {
		boolean[] d = EncodingUtils.getBinary(
				solution.getVariable(0));
		double[] f = new double[nsacks];
		double[] g = new double[nsacks];

		// calculate the profits and weights for the knapsacks
		for (int i = 0; i < nitems; i++) {
			if (d[i]) {
				for (int j = 0; j < nsacks; j++) {
					f[j] += profit[j][i];
					g[j] += weight[j][i];
				}
			}
		}

		// check if any weights exceed the capacities
		for (int j = 0; j < nsacks; j++) {
			if (g[j] <= capacity[j]) {
				g[j] = 0.0;
			} else {
				g[j] = g[j] - capacity[j];
			}
		}

		// negate the objectives since Knapsack is maximization
		solution.setObjectives(Vector.negate(f));
		solution.setConstraints(g);
	}

	@Override
	public String getName() {
		return "Knapsack";
	}

	@Override
	public int getNumberOfConstraints() {
		return nsacks;
	}

	@Override
	public int getNumberOfObjectives() {
		return nsacks;
	}

	@Override
	public int getNumberOfVariables() {
		return 1;
	}

	@Override
	public Solution newSolution() {
		Solution solution = new Solution(1, nsacks, nsacks);
		solution.setVariable(0, EncodingUtils.newBinary(nitems));
		return solution;
	}

	@Override
	public void close() {
		//do nothing
	}

}
\end{lstlisting}

It is not vitally important to understand all of the code.  Much of the code is for loading the data file discussed in the previous section.  The key sections of the code you should pay attention to are the \java{evaluate} method starting on line 168 and the \java{newSolution} method on line 219.  Starting with the \java{newSolution} method, notice how line 220 creates a solution using the three-argument constructor, \java{new Solution(1, nsacks, nsacks)}.  The three argument constructor is used to define constraints.  In this example, we are defining a problem with \java{1} decision variable, \java{nsacks} objectives, and \java{nsacks} constraints --- one objective and one constraint for each knapsack.  Then on line 221 we set the one decision variable to be a bit string (binary encoding) with \java{nitems} bits.

The \java{evaluate} method on line 168 is where the knapsack equations from the beginning of this chapter are calculated.  We extract the bit string from the solution we are evaluating on line 169.  When the bit is set to \java{1}, the corresponding item is placed in both knapsacks.  Lines 175-182 sum up the profit and weight in each knapsack.  Lines 185-191 then check if any of the weights exceeds the capacity of any knapsack.  If the weight is less than the capacity, then the constraint is satisfied as we set the constraint value to 0 (line 187).  However, if the capacity is exceeded, then the constraint is violated and we set the constraint to a non-zero value (line 189).  To reiterate, constraints that are satisfied have a value of zero; violated constraints have non-zero values (both positive and negative).

Lastly, we set the objective values on line 194 and the constraint values on line 195.  Note on line 194 how we negate the objective values.  This is because we are trying to maximize the objectives (the profits).  See \sectref{sect:maximizing} for additional details on maximizing objectives.

\section{Solving the Problem}
With the problem implemented in Java, we can now solve the multiobjective knapsack problem using the optimization algorithms provided by the MOEA Framework.  In this example, we will use the NSGA-II algorithm as shown below.  

\begin{lstlisting}[language=Java]
import java.io.File;
import java.io.IOException;
import java.io.InputStream;
import org.moeaframework.Executor;
import org.moeaframework.core.NondominatedPopulation;
import org.moeaframework.core.Solution;
import org.moeaframework.util.Vector;

/**
 * Example of binary optimization using the {@link Knapsack}
 * problem
 */
public class KnapsackExample {

	/**
	 * Starts the example running the knapsack problem.
	 * 
	 * @param args the command line arguments
	 * @throws IOException if an I/O error occurred
	 */
	public static void main(String[] args) throws IOException {			
		// solve using NSGA-II
		NondominatedPopulation result = new Executor()
				.withProblemClass(Knapsack.class,
						new File("knapsack.5.2"))
				.withAlgorithm("NSGAII")
				.withMaxEvaluations(50000)
				.distributeOnAllCores()
				.run();

		// print the results
		for (int i = 0; i < result.size(); i++) {
			Solution solution = result.get(i);
			double[] objectives = solution.getObjectives();
					
			// negate objectives to return them to their maximized
			// form
			objectives = Vector.negate(objectives);
					
			System.out.println("Solution " + (i+1) + ":");
			System.out.println("    Sack 1 Profit: " + objectives[0]);
			System.out.println("    Sack 2 Profit: " + objectives[1]);
			System.out.println("    Binary String: " +
					solution.getVariable(0));
		}
	}

}
\end{lstlisting}

Here, we are using the \java{Executor} to configure and solve the Knapsack problem.  Please refer to \chptref{chpt:executor} for more details.  You can now run this example code.  If all goes well, you will see output similar to:

\begin{lstlisting}[language=plaintext]
Solution 1:
    Sack 1 Profit: 259.0
    Sack 2 Profit: 133.0
    Binary String: 01011
\end{lstlisting}

In this case, only one Pareto optimal solution was found.  You can see the profits for each knapsack as well as identify which items were selected in this solution from the binary string being displayed.

\section{Conclusion}
This chapter walked you through a complete example of defining a new problem and solving it using the MOEA Framework.  You should now have a general understanding of using the MOEA Framework.  We recommend walking through the other examples in the \folder{examples} folder provided in the source code distribution.